package algorithms;

import java.util.ArrayList;
import java.util.List;

/**
 * @author lizen
 */
public class FuzzyMatcher {
    // 定义字符模式的内部类，包含字符和出现次数
    private static class CharPattern {
        char c;
        int count;

        CharPattern(char c, int count) {
            this.c = c;
            this.count = count;
        }
    }

    /**
     * 检查两个字符串是否模糊匹配
     * 即字符顺序和种类相同，忽略连续出现的次数差异
     */
    public static boolean isFuzzyMatch(String str1, String str2) {
        // 处理空字符串情况
        if (str1 == null && str2 == null) return true;
        if (str1 == null || str2 == null) return false;

        // 转换为字符模式列表
        List<CharPattern> pattern1 = getCharPatterns(str1);
        List<CharPattern> pattern2 = getCharPatterns(str2);

        // 模式长度不同，直接不匹配
        if (pattern1.size() != pattern2.size()) {
            return false;
        }

        // 逐个比较字符是否相同
        for (int i = 0; i < pattern1.size(); i++) {
            if (pattern1.get(i).c != pattern2.get(i).c
                    || pattern1.get(i).count > pattern2.get(i).count) {
                return false;
            }
        }

        return true;
    }

    /**
     * 将字符串转换为字符模式列表
     * 例如 "aallleenn" 转换为 [a:2, l:3, e:2, n:2]
     */
    private static List<CharPattern> getCharPatterns(String str) {
        List<CharPattern> patterns = new ArrayList<>();
        if (str.isEmpty()) {
            return patterns;
        }

        char currentChar = str.charAt(0);
        int count = 1;

        for (int i = 1; i < str.length(); i++) {
            char c = str.charAt(i);
            if (c == currentChar) {
                count++;
            } else {
                patterns.add(new CharPattern(currentChar, count));
                currentChar = c;
                count = 1;
            }
        }

        // 添加最后一个字符模式
        patterns.add(new CharPattern(currentChar, count));

        return patterns;
    }

    public static void test() {
        String standard = "allen";
        String[] testCases = {
                "allen",    // 完全匹配
                "aallen",   // a多一个
                "alllen",   // l多一个
                "alleen",   // e多一个
                "allenn",   // n多一个
                "aallleenn",// 所有字符都多一个
                "alen",     // 少一个l, false
                "alln",     // 少一个e, false
                "allex",    // 最后一个字符不同, false
                "xllen"     // 第一个字符不同, false
        };

        for (String test : testCases) {
            boolean match = isFuzzyMatch(standard, test);
            System.out.printf("'%s' 与 '%s' 匹配: %b%n", standard, test, match);
        }
    }
}
